package JZ_Offer.dataStructure.tree;

import base.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 把二叉树打印成多行
 *
 * 给定一个节点数为 n 二叉树，要求从上到下按层打印二叉树的 val 值，同一层结点从左至右输出，每一层输出一行，将输出的结果存放到一个二维数组中返回。
 */
public class JZ78_把二叉树打印成多行 {

    private static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        if (pRoot == null) {
            return lists;
        }
        layerPrint(lists, 0, pRoot);
        return lists;
    }

    private static void layerPrint(ArrayList<ArrayList<Integer>> lists, int level, TreeNode node) {
        if (node == null) {
            return;
        }

        if (level >= lists.size()) {
            ArrayList<Integer> objects = new ArrayList<>();
            objects.add(node.val);
            lists.add(objects);
        } else {
            ArrayList<Integer> objects = lists.get(level);
            objects.add(node.val);
        }

        layerPrint(lists, level + 1, node.left);
        layerPrint(lists, level + 1, node.right);
    }

    private static ArrayList<ArrayList<Integer>> Print1(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        if (pRoot == null) {
            return lists;
        }

        Deque<TreeNode> deque = new LinkedList<>();
        deque.addLast(pRoot);

        int level = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.pollFirst();
                if (node != null) {
                    deque.addLast(node.left);
                    deque.addLast(node.right);
                    if (level >= lists.size()) {
                        ArrayList<Integer> objects = new ArrayList<>();
                        objects.add(node.val);
                        lists.add(objects);
                    } else {
                        ArrayList<Integer> objects = lists.get(level);
                        objects.add(node.val);
                    }
                }
            }

            level++;
        }

        return lists;
    }

    public static void main(String[] args) {
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(5);
        TreeNode f = new TreeNode(6);
        TreeNode g = new TreeNode(7);

        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;

        ArrayList<ArrayList<Integer>> lists = Print1(a);

        System.out.println();
    }

}
